Tỉnh được thành lập sau phân chia Ba Lan lần thứ ba, được hình thành từ các tỉnh Bracław và Podole trước đây của Ba Lan, là một phần của krai Tây Nam cùng với tỉnh Volhynia và tỉnh Kiev. Thủ phủ của tỉnh được đặt tại Kamianets-Podilskyi, sau đó chuyển đến Vinnytsia. Tỉnh vẫn tồn tại cho đến cuộc cải cách hành chính của Cộng hòa Xã hội chủ nghĩa Xô viết Ukraina, giải thể tỉnh thành năm okruha.

Tỉnh Podolia chiếm giữ vùng biên giới phía tây nam của Đế quốc Nga, giáp với Áo-Hung và có diện tích khoảng 42.000 km². Trung tâm hành chính là Kamenets-Podolskiy cho đến năm 1914, sau đó chuyển đến Vinnytsia.

Tỉnh Podolia là một trong ba tỉnh của chính quyền krai Tây Nam. Năm 1917, nó được Chính phủ lâm thời Nga công nhận được quản lý bởi Tổng ban bí thư Ukraina với tư cách là đại diện của Chính phủ lâm thời Nga trong khu vực.